package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 最小子数组长度查找器
 * 
 * @author csy
 * @date 2022/7/26 15:53
 * @description 给定一个含有 n 个正整数的数组和一个正整数 target，
 *              找出该数组中满足其和 ≥ target 的长度最小的连续子数组，
 *              并返回其长度。如果不存在符合条件的子数组，返回 0。
 * 
 *              解题思路：
 *              1. 使用滑动窗口法，维护一个可变大小的窗口
 *              2. 右指针不断向右移动，将数字加入窗口
 *              3. 当窗口内数字和超过目标值时，记录当前长度，并尝试缩小窗口
 *              4. 左指针向右移动，直到和小于目标值
 * 
 *              时间复杂度：O(n)，其中n为数组长度
 *              空间复杂度：O(1)
 * 
 *              参考：https://www.programmercarl.com/0209.长度最小的子数组.html
 */
public class MinLengthSubArray {

    /**
     * 主方法：用于测试算法的效果
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 测试用例1：标准情况
        int[] nums1 = { 2, 3, 1, 2, 4, 3 };
        int target1 = 7;
        System.out.println("测试用例1：");
        System.out.println("数组：" + Arrays.toString(nums1));
        System.out.println("目标值：" + target1);
        int result1 = minSubArrayLen(target1, nums1);
        System.out.printf("数组中满足和≥%d的最小连续子数组长度为：%d%n", target1, result1);
        System.out.println("满足条件的子数组示例：" + findSubArray(nums1, target1, result1));
        
        // 测试用例2：不存在满足条件的子数组
        int[] nums2 = { 1, 1, 1, 1 };
        int target2 = 10;
        System.out.println("\n测试用例2：");
        System.out.println("数组：" + Arrays.toString(nums2));
        System.out.println("目标值：" + target2);
        int result2 = minSubArrayLen(target2, nums2);
        System.out.printf("数组中满足和≥%d的最小连续子数组长度为：%d%n", target2, result2);
        
        // 测试用例3：边界情况 - 单个元素就满足条件
        int[] nums3 = { 5, 1, 3, 8, 2 };
        int target3 = 8;
        System.out.println("\n测试用例3：");
        System.out.println("数组：" + Arrays.toString(nums3));
        System.out.println("目标值：" + target3);
        int result3 = minSubArrayLen(target3, nums3);
        System.out.printf("数组中满足和≥%d的最小连续子数组长度为：%d%n", target3, result3);
        System.out.println("满足条件的子数组示例：" + findSubArray(nums3, target3, result3));
    }

    /**
     * 查找满足和大于等于目标值的最小连续子数组长度
     * 
     * 算法核心思想：
     * 1. 使用滑动窗口技术，通过两个指针（左右边界）维护一个窗口
     * 2. 右指针不断向右扩展窗口，增加窗口内的元素和
     * 3. 当窗口内元素和大于等于目标值时，记录当前窗口长度
     * 4. 然后尝试缩小窗口：左指针右移，直到窗口和小于目标值
     * 5. 重复步骤2-4，直到右指针到达数组末尾
     * 
     * 举例说明：
     * 数组 [2,3,1,2,4,3]，目标值 7
     * 1. 初始状态：left=0, right=0, sum=2, minLen=∞
     * 2. 右移right到1：sum=5, 小于7，继续右移
     * 3. 右移right到2：sum=6, 小于7，继续右移
     * 4. 右移right到3：sum=8, 大于等于7，记录长度4，左移left
     * 5. 左移left到1：sum=6, 小于7，停止左移，继续右移right
     * 6. 右移right到4：sum=10, 大于等于7，记录长度4，左移left
     * 7. 左移left到3：sum=7, 等于7，记录长度3，左移left
     * 8. 左移left到4：sum=4, 小于7，停止左移，继续右移right
     * 9. 右移right到5：sum=7, 等于7，记录长度2，左移left
     * 10. 最终结果：minLen=2
     *
     * @param target 目标值
     * @param nums   输入数组
     * @return 满足条件的最小子数组长度，如果不存在返回0
     */
    public static int minSubArrayLen(int target, int[] nums) {
        // 初始化窗口左边界
        int left = 0; 
        // 初始化当前窗口内的数字之和
        int currentSum = 0; 
        // 初始化最小子数组长度为最大整数值（表示尚未找到满足条件的子数组）
        int minLength = Integer.MAX_VALUE; 

        // 使用滑动窗口，右边界不断向右扩展
        for (int right = 0; right < nums.length; right++) {
            // 将当前元素加入窗口和
            currentSum += nums[right];

            // 当窗口内元素和大于等于目标值时，尝试缩小窗口
            while (currentSum >= target) {
                // 更新最小长度（当前窗口大小为right-left+1）
                minLength = Math.min(minLength, right - left + 1);
                // 移除窗口最左侧元素，并将左边界右移
                currentSum -= nums[left++];
            }
        }

        // 如果minLength仍为初始值，说明没有找到满足条件的子数组，返回0
        // 否则返回找到的最小长度
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
    
    /**
     * 辅助方法：查找并返回满足条件的子数组
     * 此方法仅用于演示，返回第一个找到的满足条件的子数组
     * 
     * @param nums 原始数组
     * @param target 目标值
     * @param minLen 最小子数组长度
     * @return 满足条件的子数组的字符串表示
     */
    private static String findSubArray(int[] nums, int target, int minLen) {
        // 如果不存在满足条件的子数组，返回空字符串
        if (minLen == 0) {
            return "不存在满足条件的子数组";
        }
        
        int left = 0;
        int sum = 0;
        
        // 查找第一个满足条件的子数组
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            
            // 尝试缩小窗口
            while (sum >= target && right - left + 1 >= minLen) {
                // 如果找到长度等于minLen的子数组，返回它
                if (right - left + 1 == minLen) {
                    int[] subArray = Arrays.copyOfRange(nums, left, right + 1);
                    return Arrays.toString(subArray) + "，和为" + sum;
                }
                sum -= nums[left++];
            }
        }
        
        return "未找到满足条件的子数组";
    }
}